\chapter{Лекция 2}

\section{В предыдущей серии}

Было введено понятия специализатора $$Mix^L_T \left(p_L |_x\right) = \lambda y . p_L |_x \left(y\right)$$.

Понятие программы генерирующей расширения $$G_{p_L}\left(x\right) = p_L |_x$$ - т. е. программа, которая по заданному значению аргумента, построит программу, которая
вычисляет исходную функцию от заданного аргумента.

Было введено понятие интерпритатора $$Int^L_T \left(p_L, x\right) = p_L\left(x\right)$$

\section{Проекции Футамуры-Ершова}

$$Mix^M_{MM} \left(Int^L_M , p_L\right) = \lambda x . Int^L_M \left(p_L, x\right)$$
\label{math::eq1}

получаем программу на языке $M$.

\begin{Def}
Первая проекция Футамуры. Специализация интерпритатора на программу есть запись этой программы в языке реализации интерпритатора. (см. \ref{math::eq1})
\end{Def}

$$Mix^{MM}_{MMM}\left(Mix^M_{MM}, Int^L_M\right) = \lambda p_L . Mix^M_{MM}\left(Int^L_M , p_L\right)$$
\label{math::eq2}

получаем транслятор с языка $L$ на язык $M$.

\begin{Def}
Вторая проекция Футамуры. Специализация специализатора на интерпритатор есть компилятор интерпритируемого языка на язык реализация интерпритатора.
(см. \ref{math::eq2})
\end{Def}

$$Mix^{MMM}_{MMMM}\left(Mix^{MM}_{MMM}, Mix^M_{MM}\right) = \lambda Int^L_M . Mix^{MM}_{MMM}\left(Mix^M_{MM}, Int^L_M\right)$$
\label{math::eq3}

получили генератор компиляторов.

\begin{Def}
Третья проекция Футамуры. Специализация специализатора на специализатор дает генератор компиляторов по интепритатору. Этот генератор действует из интепритируемого
языка в язык реализации компилятора. (см. \ref{math::eq3})
\end{Def}

\section{Синтаксис}

\subsection{Вводные определения}

\begin{Def}
Конечное множество $X$ --- алфавит.
\end{Def}

\begin{Def}
Цепочка (слова) --- отобржаение из префикса натурального (с нулем) ряда в алфавит: $$\left[0,n\right] \rightarrow X$$ (или на пальцах последовательность из $n+1$
символов алфавита $x_0x_1...x_n$). Длинной цепочки $x_0x_1...x_n$ называется $$\left|x_0x_1...x_n\right| = n+1$$.

Пустая цепочка $\varepsilon : \left[0, -1\right] \rightarrow X$, длинна такой цепочки $\left|\varepsilon\right| = 0$
\end{Def}

\begin{Def}
Конкатенация цепочкек $a = a_0a_1...a_{m}$ и $b = b_0b_1...b_{n}$ --- цепочка $c = ab = a_0a_1...a_{m}b_0b_1...b_{n}$
\end{Def}

\begin{Def}
Множество всех цепочек над алфавитом $X$ обозначется как $X^*$
\end{Def}

\begin{Def}
Операция возведения в степень для цепочки $w$ определим следющим образом:
\begin{itemize}
\item $w^0 = \varepsilon$

\item $w^{n+1} = ww^{n}$
\end{itemize}
\end{Def}

\begin{Def}
Цепочка $x$ является префиксом цепочки $y$, если существует цепочка $z$ (возможно пустая), такая что $y = xz$. Аналогичным образом определяется суффикс.
\end{Def}

\paragraph{Примечание:} множество всех цепочек образует моноид относительно конкатенации.

\begin{Def}
Цепочка $x$ является подцепочкой цепочки $y$, если существуют цепочки $u$ и $v$ (возможно пустые), такие что $y = uxv$.
\end{Def}

\subsection{Абстрактный синтаксис}

Пусть $P$ - некоторый алфавит. Рассмотрим множество $C \subset P*$, для которого справедливы:
\begin{itemize}
\item если $x \in C$, то и все префиксы $x$ лежат в $C$

\item $\forall w,u \not= \varepsilon \in C \exists v \not= \varepsilon : v$ является префиксом одновременно для $w$ и $u$ 
\end{itemize}

\paragraph{Пример:}
TBD вставить картинку с примером дерева для алфавита $P = \{s,l,r\}$

Пусть теперь имеется некоторый алфавит пометок $\Omega$, а помеченное дерево на вершинах $C$ --- $C + l: C \rightarrow \Omega$, т. е. каждая вершина дерева
имеет пометку.

\paragraph{Пример:}
TBD вставить картинку с помеченными деревьями при алфавите пометок $\Omega = \{x,y,z,+,-\}$

В последнем примере видно, что если интерпритировать пометки, то не все деревья будут иметь смысл, способ отделять значимые деревья от незнаимых (полезные
от бесполезных) есть способ задания синтаксиса.

\paragraph{Пример:}
Возьмем множество $\Omega = \mathbb{Z}\cup X=\{x_1,x_2,...\}\cup O=\{+,-,*,...\}$ и составим рекуррентное соотношение на деревья: $E = \mathbb{Z}\cup X\cup O\left(E,E\right)$,
где $O\left(E,E\right)$ - правильные деревья сформированные через объединение правильных деревьев корнем из множества O.

TBD вставить картинку для объяснения $O\left(E,E\right)$

Как решить это рекурсивное уравнение? Рассмотрим правую часть как функцию от множества правильных деревьев, т. е. следующим образом:
$$\lambda \epsilon . \mathbb{Z}\cup X\cup O\left(\epsilon,\epsilon\right)$$,
где $\epsilon$ - правильные деревья. На начальном этапе эти деревья просто числа и переменные, далее получаем новое множество деревьев, потом вновь полученное
множество подставляем в уравнение, и так далее мы наращиваем множество правильных деревьев:
$$F\left(\epsilon\right) = \mathbb{Z}\cup X\cup O\left(\epsilon, \epsilon\right) = \epsilon$$, т. е. ренешием является множество неподвижных точек правой части
уравнения.

\begin{Th}
Пусть $F$ - монотонная функция, тогда $X$ --- $F$-замкнутое множество тогда и только тогда, когда $F\left(X\right) \subseteq X$.
$$\cap_i \{X_i | F\left(X_i\right) \subseteq X_i\}$$ --- наименьшее $F$-замкнутое множество (пересечение $F$-замкнутых множеств) есть наименьшая неподвижная точка.
\end{Th}

\begin{Proof}
Хотим доказать, что это пересечение также является замкнутым множеством, что дает нам доказательство исхождного утверждения, т. е
$$F\left(\cap X_i\right) \subseteq \cap X_i$$

Во-первых, $X_i \supseteq \cap X_i \Rightarrow F\left(X_i\right) \supseteq F\left(\cap X_i\right)$

Во-вторых, $\cap F\left(X_i\right) \supseteq F\left(\cap X_i\right)$, а с другой стороны $\cap F\left(X_i\right) \subseteq \cap X_i$, что и требовалось.
\end{Proof}

Что в итоге нам это все дает? Решение исходного уравнения можно строить итеративно следующим образом:

\[
	\begin{split}
		&E_0 = X\cup \mathbb{Z}\\
		&E_1 = E_0\cup O\left(E_0,E_0\right)\\
		&E_2 = E_1\cup O\left(E_1,E_1\right)\\
		& ... \\
	\end{split}
\]

\subsection{Учебный язык и его синтаксис}

Введем учебный язык $L$ с помощью некоторого абстрактного синтаксиса:

\begin{itemize}
\item $X = \{x_1, x_2, ... \}$ - множество переменных

\item $\mathbb{Z}$ - множество констант

\item $O=\{+,-,...\}$ - набор примитивных операций

\item $\mathbb{R} = \{IF, FUN, APPLY, DEF\}$ - начальное множество символов (судя по всему элементарных конструкций языка, ветвление, функция и "применение")

\item $E = X\cup\mathbb{Z}\cup O\left(E,E\right)\cup IF\left(E,E,E\right)\cup FUN\left(X,E\right)\cup APPLY\left(E,E\right)$

\item $P = DEF\left(X,E,P\right)\cup\varepsilon$ - программа или начальное состояние.
\end{itemize}

Программа представляет из себя набор поименнованных выражений.

Теперь опишем операционную семантику языка $L$.

\begin{itemize}
\item Состояние это отображение $S : X \rightarrow E$, т. е. набор соответствий между переменными и выражениями. Постановка состояния обозначается так:
$S\left[x \leftarrow E\right] = \lambda y . iif~\left(y\not=x\right)~S\left(y\right)~E$

\item $\left[z \in \mathbb{Z}\right] = z$, семантика целочисленной константы, есть просто сама константа.

\item $defun\left(E\right) = iif~\left(E=FUN\left(x,e\right)\right)~\left(x,e\right)~\left(undefined\right)$ - возвращает пару (тело функции и аргумент, если $E$ - функция)

\item $deint\left(E\right) = iif~\left(E=z\in\mathbb{Z}\right)~\left(z\right)~\left(undefined\right)$ - возвращает значение $E$, если $E$ - число.

\item $subst\left(S\in E, x\in X, \varepsilon\in E\right)$, если $S = O\left(y,z\right)$, то $O\left(subst\left(y,x,\varepsilon\right),subst\left(z,x,\varepsilon\right)\right)$,
если $S=IF\left(c,y,z\right)$, то $IF\left(subst\left(c,x,\varepsilon\right),subst\left(y,x,\varepsilon\right),subst\left(z,x,\varepsilon\right)\right)$, и тд меняем все
свободные вхождения переменной $x$ на $\varepsilon$
\end{itemize}

Требуется написать в любимом языке структуру данных представляющую абстрактное синтаксическое дерево, напечатать дерево в конкретном синтаксисе, создать
интерпритатор согласно семантике языка.